package com.gxc.tree;

/**
 * 找到一棵二叉树中，最大的搜索二叉子树，返回最大搜索二叉子树的节点个数
 *
 * 解法：
 * 树的递归问题：
 * 包含树头和不包含树头
 */
public class MaxBST {

    public int maxBST(TreeBean head) {
        if (head == null) return 0;

        Info info = process(head);
        return info.maxSize;
    }

    private Info process(TreeBean node) {
        if (node == null) {
            return new Info(true, Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
        }

        Info left = process(node.left);
        Info right = process(node.right);

        /**
         * 如果左右子树都是二叉搜索树，当前节点比左子树的最大值打，比右子树的最小值小，则加上当前节点后也是二叉搜索树
         */
        boolean isBST = node.value>left.max && node.value>right.min &&
                left.isBST && right.isBST;
        int maxSize = isBST?(left.maxSize + right.maxSize +1):(Math.max(left.maxSize, right.maxSize)+1);
        return new Info(isBST, right.max, left.min, maxSize);
    }

    public class Info {

        /**
         * 是否是二叉搜索树
         */
        public boolean isBST;
        /**
         * 左数最大的值
         */
        public int max;
        /**
         * 右数最小的值
         */
        public int min;
        /**
         * 最大搜索二叉子树的节点个数
         */
        public int maxSize;

        public Info(boolean isBST, int max, int min, int maxSize) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
            this.maxSize = maxSize;
        }
    }
}
